package Tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class leet_113 {
}

class Solution_113 {

    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> tmpList = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<Integer> tmpList = new ArrayList<>();
        DFS(root, targetSum);
        return result;
    }

    /**
     * 利用DFS找到每一个节点的关系
     * 前序遍历 当找到值等于目标或者大于目标值时跳出 当等于是就添加进结果
     * @param root
     * @param targetSum
     * @return
     */
    public void DFS(TreeNode root, int targetSum){
        if(root==null){
            return;
        }

        // 节点值
        tmpList.add(root.val);
        int value = 0;
        for(int i=0; i<tmpList.size(); i++){
            value = value + tmpList.get(i);
        }
        if(value==targetSum && root.left==null && root.right==null){
            result.add(new ArrayList<>(tmpList));
        }

        DFS(root.left, targetSum);
        DFS(root.right, targetSum);
        tmpList.remove(tmpList.size()-1);

    }
}
